/******************************************************************************
 This is a derivative work of the data structure presented in:
 
 http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html

 whose author is Brad Appleton (http://www.bradapp.net/). 
 
 See License.txt for license information about the use of the data
 structure.

 Please, note the links above were valid when this comment was written and 
 may not be valid at the time you read it.
 ******************************************************************************/

#ifndef AVL_ITERATOR_H
#define AVL_ITERATOR_H

#include <utility>
#include <algorithm>
#include <exception>
#include <boost/call_traits.hpp>
#include <boost/iterator_adaptors.hpp>  // for iterator_adaptor<>
#include <boost/utility/enable_if.hpp>
#include <boost/shared_ptr.hpp>

#include "avl.h"
#include "tst_avl_pair.h"

namespace cnome { namespace tst_avl {
namespace impl{
template <typename StringT, typename T, typename Pred, typename Alloc>
struct tst_avl_iterator_impl {

    typedef typename StringT::value_type char_t;

    typedef pair_tst_avl<StringT, T> pair_t;

    typedef boost::bidirectional_traversal_tag iterator_category;
    typedef pair_t                       value_type;
    typedef std::size_t                  difference_type;
    typedef pair_t*                      pointer;
    typedef pair_t&                      reference;
    typedef pair_t const&                const_reference;

    typedef boost::shared_ptr<value_type> value_type_ptr;

    static const unsigned char OUTDATED_NONE = 0x00;
    static const unsigned char OUTDATED_KEY  = 0x01;
    static const unsigned char OUTDATED_DATA = 0x02;
    static const unsigned char OUTDATED_ALL  = 0x03;

    value_type_ptr value;
    StringT        valueFirst;
    unsigned char  outDated;

    avlNode<char_t, T, Pred, Alloc>* ptrNode;

    tst_avl_iterator_impl(): value(), valueFirst(), outDated(OUTDATED_ALL), ptrNode(0) {}
    tst_avl_iterator_impl(const avlTree<char_t, T, Pred, Alloc>* itR)
        : value(), valueFirst(), outDated(OUTDATED_ALL), ptrNode(const_cast<avlNode<char_t, T, Pred, Alloc>*>(itR->nillNode)) {}
    tst_avl_iterator_impl(const tst_avl_iterator_impl& other)
        : value(other.value), valueFirst(other.valueFirst), outDated(other.outDated), ptrNode(other.ptrNode) {}
    ~tst_avl_iterator_impl() {}

    bool operator== (tst_avl_iterator_impl const& other) const { 
        return ptrNode == other.ptrNode;
    }
    
    tst_avl_iterator_impl& operator= (const tst_avl_iterator_impl& right) {
#ifndef KEEP_ITER_KEY_UPDATED_AS_POSSIBLE
        outDated = OUTDATED_ALL;
#else
        outDated = right.outDated;
        if ((outDated&OUTDATED_KEY)!=OUTDATED_KEY)
            valueFirst = right.valueFirst;
#endif
        ptrNode = right.ptrNode;
        
        return *this;
    }

    reference operator* () {
        if (outDated) {
            if (ptrNode->isNill())
                throw std::bad_exception();
            else {
#ifndef KEEP_ITER_KEY_UPDATED_AS_POSSIBLE
                if ((outDated&OUTDATED_KEY)==OUTDATED_KEY)
#endif
                    updateValueFirst();
                value = value_type_ptr(make_pair_tst_avl_ptr(valueFirst, *ptrNode->getData(), true));
            }
            outDated = OUTDATED_NONE;
        }

        return *value;
    }

    reference operator* () const {
        return **const_cast<tst_avl_iterator_impl*>(this);
    }

    reference dereference() { return **const_cast<tst_avl_iterator_impl*>(this); }

    const_reference dereference() const{ return **const_cast<tst_avl_iterator_impl*>(this); }

    void clear() {
        valueFirst.clear();
        outDated = OUTDATED_ALL;
    }

    tst_avl_iterator_impl& operator++ () { advance(); return *this; }

    bool is_atend() const { return ptrNode->isNill(); }

    void moveToChild(dir_t dir) {
        ptrNode = ptrNode->subtree(dir);
    }

    void moveToParent() {
        if (ptrNode->isNill())
            return;

        ptrNode = ptrNode->parent->isNill()?ptrNode->parent->parent:ptrNode->parent->myLinkInParent();
    }

    void advance() {
        if (is_atend())
            return;

        outDated = OUTDATED_ALL;
        dir_t d;
        for (d = MIDDLE; d <= RIGHT && !ptrNode->subtree(d); d = dir_t(d+1));
        do {
            if (d <= RIGHT) {
                do {
                    moveToChild(d);
                    for (d = LEFT; d <= RIGHT && !ptrNode->subtree(d); d = dir_t(d+1));
                    if (ptrNode->getData() && d > LEFT)
                        return;
                }while (d <= RIGHT);
            }
            else {
                do {
                    d = ptrNode->myDirInParent();
                    moveToParent();
                    if (is_atend())
                        return;
                    for (d = dir_t(d+1); d <= RIGHT && !ptrNode->subtree(d) && !(d == MIDDLE && ptrNode->getData()); d = dir_t(d+1));
                }
                while(!is_atend() && d > RIGHT);
                if (ptrNode->getData() && d == MIDDLE)
                    return;
            }
        } while(!is_atend());
    }

    void goFirstOne() {
        if (is_atend())
            return;

        outDated = OUTDATED_ALL;
        dir_t d;
        do {
            for (d = LEFT; d <= RIGHT && !ptrNode->subtree(d); d = dir_t(d+1));
            if (d > RIGHT || (d > LEFT && ptrNode->getData()))
                break;
            moveToChild(d);
        }while (ptrNode);

    }

    void goLastOne() {
        if (is_atend())
            return;

        outDated = OUTDATED_ALL;
        dir_t d;
        do {
             for (d = RIGHT; d >= LEFT && !ptrNode->subtree(d); d = dir_t(d-1));
             if (d < LEFT || (d == LEFT && ptrNode->getData()))
                break;
            moveToChild(d);
        }while (ptrNode);

   }

    void recede() {
        if (is_atend()) {
            ptrNode = ptrNode->subtree(MIDDLE);
            goLastOne();
            return;
        }

        outDated = OUTDATED_ALL;
        dir_t d = LEFT;
        for (; d >= LEFT && !ptrNode->subtree(d); d = dir_t(d-1));
        do {
            if (d >= LEFT) {
                ptrNode = ptrNode->subtree(d);
                goLastOne();
                if (ptrNode->getData())
                    return;
                for (d = dir_t(ptrNode->myDirInParent()-1); d >= LEFT && !ptrNode->subtree(d); d = dir_t(d-1));
            }
            else {
                do {
                    d = ptrNode->myDirInParent();
                    moveToParent();
                    if (is_atend())
                        return;
                    if (d == MIDDLE && ptrNode->getData())
                        return;
                    d = dir_t(d-1);
                }
                while(!is_atend() && d <= LEFT);
                for (; d >= LEFT && !ptrNode->subtree(d) && !(d == MIDDLE && ptrNode->getData()); d = dir_t(d-1));
                if (d == MIDDLE && ptrNode->getData() && !ptrNode->subtree(MIDDLE))
                    return;
            }
        } while(!is_atend());
    }

    void updateValueFirst() {
        valueFirst = "";
        std::list<avlNode<char_t, T, Pred, Alloc>*> nodesLst;
        avlNode<char_t, T, Pred, Alloc>* node = ptrNode;
        if (node->isNill())
            return;
        nodesLst.push_back(node);
        for(;;) {
            dir_t dir = node->myDirInParent();
            node = node->parent;
            if (node->isNill())
                break;
            if (dir == MIDDLE)
                nodesLst.push_back(node);
        } 
        while (nodesLst.size()) {
            for (std::size_t i = 0; i < nodesLst.back()->keySize(); i++)
                valueFirst += nodesLst.back()->keyAddress()[i];
            nodesLst.pop_back();
        }
    }
};
}

template <typename StringT, typename T, typename Pred, typename Alloc>
class tst_avl_iterator
    : public boost::iterator_adaptor<
          tst_avl_iterator<StringT, T, Pred, Alloc>  // Derived
        , impl::tst_avl_iterator_impl<StringT, T, Pred, Alloc>   // Base
        , boost::use_default                  // Value
        , boost::forward_traversal_tag        // CategoryOrTraversal
    > {
    typedef impl::tst_avl_iterator_impl<StringT, T, Pred, Alloc> base_t;
    typedef tst_avl_iterator derived_t;
    typedef typename StringT::value_type char_t;

private:
    struct enabler {};  // a private type avoids misuse

public:
    tst_avl_iterator()
        : tst_avl_iterator::iterator_adaptor_() {}

    explicit tst_avl_iterator(base_t p)
        : tst_avl_iterator::iterator_adaptor_(p) {}

    tst_avl_iterator(const tst_avl_iterator& other)
        : tst_avl_iterator::iterator_adaptor_(other.base()) {}

    template <typename OtherStringT, typename OtherT, typename OtherPred, typename OtherAlloc>
    tst_avl_iterator(
        tst_avl_iterator<StringT, OtherT, OtherPred, OtherAlloc> const& other
        , typename boost::enable_if<
        boost::is_convertible<tst_avl_iterator<OtherStringT, OtherT, OtherPred, OtherAlloc>, tst_avl_iterator<StringT, T, Pred, Alloc> >
        , 
        enabler
        >::type = enabler()
        )
        : derived_t::iterator_adaptor_(other.base()) {}

    tst_avl_iterator(const avlTree<char_t, T, Pred, Alloc>* avlTree)
        : tst_avl_iterator::iterator_adaptor_(avlTree) {
    }

    tst_avl_iterator& operator= (const tst_avl_iterator& other) {
        const_cast<base_t&>(this->base()) = const_cast<base_t&>(other.base());
        
        return *const_cast<tst_avl_iterator*>(this);
    }

private:
    friend class boost::iterator_core_access;
    void increment() { const_cast<base_t&>(this->base()).advance(); }
    void decrement() { const_cast<base_t&>(this->base()).recede(); }
};
}}  // cnome::tst_avl

#endif
